{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #守护太空城"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: defendSpaceCity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #守护太空城"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>各位勇者请注意，力扣太空城发布陨石雨红色预警。</p>\n",
    "\n",
    "<p>太空城中的一些舱室将要受到陨石雨的冲击，这些舱室按照编号 <code>0 ~ N</code>&nbsp;的顺序依次排列。为了阻挡陨石损毁舱室，太空城可以使用能量展开防护屏障，具体消耗如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择一个舱室开启屏障，能量消耗为 <code>2</code></li>\n",
    "\t<li>选择相邻两个舱室开启联合屏障，能量消耗为 <code>3</code></li>\n",
    "\t<li>对于已开启的&nbsp;<strong>一个&nbsp;</strong>屏障，<strong>多维持一时刻</strong>，能量消耗为 <code>1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>已知陨石雨的影响范围和到达时刻，<code>time[i]</code>&nbsp;和 <code>position[i]</code>&nbsp;分别表示该陨石的到达时刻和冲击位置。请返回太空舱能够守护所有舱室所需要的最少能量。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>同一时间，一个舱室不能被多个屏障覆盖</li>\n",
    "\t<li>陨石雨仅在到达时刻对冲击位置处的舱室有影响</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "输入：time = [1,2,1], position = [6,3,3]\n",
    "\n",
    "输出：5\n",
    "\n",
    "解释：时刻 1，分别开启编号 3、6 舱室的屏障，能量消耗 2*2 = 4。时刻 2，维持编号 3 舱室的屏障，能量消耗 1。因此，最少需要能量 5。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "输入：time = [1,1,1,2,2,3,5], position = [1,2,3,1,2,1,3]\n",
    "\n",
    "输出：9\n",
    "\n",
    "解释：时刻 1，开启编号 1、2 舱室的联合屏障，能量消耗 3。时刻 1，开启编号 3 舱室的屏障，能量消耗 2 。时刻 2，维持编号 1、2 舱室的联合屏障，能量消耗 1。时刻 3，维持编号 1、2 舱室的联合屏障，能量消耗 1。时刻 5，重新开启编号 3 舱室的屏障，能量消耗 2。因此，最少需要能量 9。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= time.length == position.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= time[i] &lt;= 5</code></li>\n",
    "\t<li><code>0 &lt;= position[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [EJvmW4](https://leetcode.cn/problems/EJvmW4/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [EJvmW4](https://leetcode.cn/problems/EJvmW4/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1]\\n[6,3,3]', '[1,1,1,2,2,3,5]\\n[1,2,3,1,2,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\n",
    "        n, m = max(position) , 1 << max(time)\n",
    "        rain = [0] * (n + 1)\n",
    "        for t, p in zip(time, position):\n",
    "            rain[p] |= 1 << (t - 1)\n",
    "\n",
    "        union = [0] * m\n",
    "        single = [0] * m\n",
    "        for i in range(1, m):\n",
    "            lb = i & -i\n",
    "            j = i ^ lb\n",
    "            lb2 = j & -j\n",
    "            # 定义两类屏障\n",
    "            union[i] = union[j] + (1 if lb == (lb2 >> 1) else 3) # lb == (lb2 >> 1) 表示两个时间点相邻\n",
    "            single[i] = single[j] + (1 if lb == (lb2 >> 1) else 2) # 递推\n",
    "        f = [[inf] * m for _ in range(n + 1)]\n",
    "        for j in range(m):\n",
    "            f[0][j] = union[j] + single[((m - 1) ^ j) & rain[0]]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m):\n",
    "                pre = mask = (m - 1) ^ j\n",
    "                while True: # 枚举j的补集mask中的子集pre\n",
    "                    cost = f[i - 1][pre] + union[j] + single[(mask ^ pre) & rain[i]]\n",
    "                    f[i][j] = min(f[i][j], cost) # 状态转移\n",
    "                    if pre == 0:\n",
    "                        break\n",
    "                    pre = (pre - 1) & mask\n",
    "        return f[n][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\r\n",
    "        n, m = max(position), 1 << max(time)\r\n",
    "        rain = [0] * (n + 1)\r\n",
    "        for t, p in zip(time, position):\r\n",
    "            rain[p] |= 1 << (t - 1)\r\n",
    "\r\n",
    "        union = [0] * m\r\n",
    "        single = [0] * m\r\n",
    "        for i in range(1, m):\r\n",
    "            lb = i & -i\r\n",
    "            j = i ^ lb\r\n",
    "            lb2 = j & -j\r\n",
    "            union[i] = union[j] + (1 if lb == (lb2 >> 1) else 3)  # lb == (lb2 >> 1) 表示两个时间点相邻\r\n",
    "            single[i] = single[j] + (1 if lb == (lb2 >> 1) else 2)  # 递推\r\n",
    "\r\n",
    "        f = [[inf] * m for _ in range(n + 1)]\r\n",
    "        for j in range(m):\r\n",
    "            f[0][j] = union[j] + single[((m - 1) ^ j) & rain[0]]\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            for j in range(m):\r\n",
    "                pre = mask = (m - 1) ^ j\r\n",
    "                while True:  # 枚举 j 的补集 mask 中的子集 pre\r\n",
    "                    cost = f[i - 1][pre] + union[j] + single[(mask ^ pre) & rain[i]]\r\n",
    "                    f[i][j] = min(f[i][j], cost)\r\n",
    "                    if pre == 0:\r\n",
    "                        break\r\n",
    "                    pre = (pre - 1) & mask\r\n",
    "        return f[n][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time, position):\n",
    "        n = max(position)\n",
    "        m = 1 << max(time)\n",
    "        rain = [0] * (n + 1)\n",
    "\n",
    "        for i in range(len(time)):\n",
    "            rain[position[i]] |= 1 << (time[i] - 1)\n",
    "\n",
    "        un = [0] * m\n",
    "        single = [0] * m\n",
    "        for i in range(1, m):\n",
    "            lb = i & -i\n",
    "            j = i ^ lb\n",
    "            lb2 = j & -j\n",
    "            un[i] = un[j] + (1 if lb == (lb2 >> 1) else 3)  # lb == (lb2 >> 1) 表示两个时间点相邻\n",
    "            single[i] = single[j] + (1 if lb == (lb2 >> 1) else 2)  # 递推\n",
    "\n",
    "        f = [[float('inf')] * m for _ in range(n + 1)]\n",
    "        for j in range(m):\n",
    "            f[0][j] = un[j] + single[((m - 1) ^ j) & rain[0]]\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m):\n",
    "                # 枚举 j 的补集 mask 中的子集 pre\n",
    "                mask = (m - 1) ^ j\n",
    "                pre = mask\n",
    "                while True:\n",
    "                    cost = f[i - 1][pre] + un[j] + single[(mask ^ pre) & rain[i]]\n",
    "                    f[i][j] = min(f[i][j], cost)\n",
    "                    if pre == 0:\n",
    "                        break\n",
    "                    pre = (pre - 1) & mask\n",
    "\n",
    "        return f[n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\n",
    "        n, m = max(position), 1 << max(time)\n",
    "        rain = [0] * (n + 1)\n",
    "        for t, p in zip(time, position):\n",
    "            rain[p] |= 1 << (t - 1)\n",
    "        union = [0] * m\n",
    "        single = [0] * m\n",
    "        for i in range(1, m):\n",
    "            lb = i & -i\n",
    "            j = i ^ lb\n",
    "            lb2 = j & -j\n",
    "            union[i] = union[j] + (1 if lb == (lb2 >> 1) else 3)\n",
    "            single[i] = single[j] + (1 if lb == (lb2 >> 1) else 2)\n",
    "        \n",
    "        f = [[inf] * m for _ in range(n + 1)]\n",
    "        for j in range(m):\n",
    "            f[0][j] = union[j] + single[((m-1)^j)&rain[0]]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m):\n",
    "                s = mask = (m - 1) ^ j\n",
    "                while True:\n",
    "                    cost = f[i-1][s] + union[s] + single[(mask^s)&rain[i]]\n",
    "                    f[i][j] = min(f[i][j], cost)\n",
    "                    if s == 0:\n",
    "                        break\n",
    "                    s = (s - 1) & mask\n",
    "        return f[n][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\n",
    "        n, m = max(position), 1 << max(time)\n",
    "        rain = [0] * (n + 1)\n",
    "        for t, p in zip(time, position):\n",
    "            rain[p] |= 1 << (t - 1)\n",
    "\n",
    "        union = [0] * m\n",
    "        single = [0] * m\n",
    "        for i in range(1, m):\n",
    "            lb = i & -i\n",
    "            j = i ^ lb\n",
    "            lb2 = j & -j\n",
    "            union[i] = union[j] + (1 if lb == (lb2 >> 1) else 3)  # lb == (lb2 >> 1) 表示两个时间点相邻\n",
    "            single[i] = single[j] + (1 if lb == (lb2 >> 1) else 2)  # 递推\n",
    "\n",
    "        f = [[inf] * m for _ in range(n + 1)]\n",
    "        for j in range(m):\n",
    "            f[0][j] = union[j] + single[((m - 1) ^ j) & rain[0]]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m):\n",
    "                pre = mask = (m - 1) ^ j\n",
    "                while True:  # 枚举 j 的补集 mask 中的子集 pre\n",
    "                    cost = f[i - 1][pre] + union[j] + single[(mask ^ pre) & rain[i]]\n",
    "                    f[i][j] = min(f[i][j], cost)\n",
    "                    if pre == 0:\n",
    "                        break\n",
    "                    pre = (pre - 1) & mask\n",
    "        return f[n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\n",
    "        n, m = max(position), 1 << max(time)\n",
    "        rain = [0] * (n + 1)\n",
    "        for t, p in zip(time, position):\n",
    "            rain[p] |= 1 << (t - 1)\n",
    "\n",
    "        union = [0] * m\n",
    "        single = [0] * m\n",
    "        for i in range(1, m):\n",
    "            lb = i & -i\n",
    "            j = i ^ lb\n",
    "            lb2 = j & -j\n",
    "            union[i] = union[j] + (1 if lb == (lb2 >> 1) else 3)  # lb == (lb2 >> 1) 表示两个时间点相邻\n",
    "            single[i] = single[j] + (1 if lb == (lb2 >> 1) else 2)  # 递推\n",
    "\n",
    "        f = [[inf] * m for _ in range(n + 1)]\n",
    "        for j in range(m):\n",
    "            f[0][j] = union[j] + single[((m - 1) ^ j) & rain[0]]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m):\n",
    "                pre = mask = (m - 1) ^ j\n",
    "                while True:  # 枚举 j 的补集 mask 中的子集 pre\n",
    "                    cost = f[i - 1][pre] + union[j] + single[(mask ^ pre) & rain[i]]\n",
    "                    f[i][j] = min(f[i][j], cost)\n",
    "                    if pre == 0:\n",
    "                        break\n",
    "                    pre = (pre - 1) & mask\n",
    "        return f[n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "这个可以被省略\n",
    "f[i][j],（保护前i个太空舱）大前提1，\n",
    "第i个太空舱与i+1个舱开启联合屏障的时间集合为j的话，大前提2\n",
    "最小的花费，大前提3\n",
    "守护弱智太空城，气死我了\n",
    "难写的一批\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\n",
    "        tmp=[i-1 for i in time]\n",
    "        time=tmp\n",
    "        max_time=max(time)\n",
    "        max_pos=max(position)\n",
    "        MX=1<<(max_time+1)\n",
    "        m=max_time+1\n",
    "        #预处理union和single集合,这里主要针对time枚举\n",
    "        #位置集合很好写，时间集合比较麻烦，统统减1映射,完美\n",
    "        #来到了最麻烦的地方，怎么处理维持\n",
    "        single=[0]*MX\n",
    "        union=[0]*MX\n",
    "        for x in range(0,MX):\n",
    "            #不会就暴力\n",
    "            def dfs(i:int,pre:int,state:int)->int:\n",
    "                if i==m :return 0\n",
    "                add=2 if state==0 else 3\n",
    "                if x>>i&1 :\n",
    "                    if  pre==1:\n",
    "                        return 1+dfs(i+1,1,state)\n",
    "                    else:\n",
    "                        return add+dfs(i+1,1,state)\n",
    "                else:\n",
    "                    return dfs(i+1,0,state)\n",
    "            single[x]=(x&1)*2+dfs(1,x&1,0)\n",
    "            union[x]=(x&1)*3+dfs(1,x&1,1)\n",
    "        #预处理结束，接下来写cache\n",
    "        #找到每个pos被袭击的集合\n",
    "        protect=[0]*(max_pos+1)\n",
    "        for i,t in enumerate(time):\n",
    "            protect[position[i]]+=(1<<t)\n",
    "        #真是太麻了，应该注意到前面的太空舱如果不开屏障的话，后面就没机会了，所以应该写个dp之类的会更好一些\n",
    "        f = [[inf] * MX for _ in range(max_pos + 1)]\n",
    "        for j in range(MX):\n",
    "            f[0][j] = union[j] + single[((MX - 1) ^ j) & protect[0]]\n",
    "        for i in range(1, max_pos + 1):\n",
    "            for j in range(MX):\n",
    "                pre = mask = (MX - 1) ^ j\n",
    "                while True:  # 枚举 j 的补集 mask 中的子集 pre\n",
    "                    cost = f[i - 1][pre] + union[j] + single[(mask ^ pre) & protect[i]]\n",
    "                    f[i][j] = min(f[i][j], cost)\n",
    "                    if pre == 0:\n",
    "                        break\n",
    "                    pre = (pre - 1) & mask\n",
    "        return f[max_pos][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "这个可以被省略\n",
    "f[i][j],（保护前i个太空舱）大前提1，\n",
    "第i个太空舱与i+1个舱开启联合屏障的时间集合为j的话，大前提2\n",
    "最小的花费，大前提3\n",
    "守护弱智太空城，气死我了\n",
    "难写的一批\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\n",
    "        tmp=[i-1 for i in time]\n",
    "        time=tmp\n",
    "        max_time=max(time)\n",
    "        max_pos=max(position)\n",
    "        MX=1<<(max_time+1)\n",
    "        m=max_time+1\n",
    "        #预处理union和single集合,这里主要针对time枚举\n",
    "        #位置集合很好写，时间集合比较麻烦，统统减1映射,完美\n",
    "        #来到了最麻烦的地方，怎么处理维持\n",
    "        single=[0]*MX\n",
    "        union=[0]*MX\n",
    "        for x in range(0,MX):\n",
    "            #不会就暴力\n",
    "            def dfs(i:int,pre:int,state:int)->int:\n",
    "                if i==m :return 0\n",
    "                add=2 if state==0 else 3\n",
    "                if x>>i&1 :\n",
    "                    if  pre==1:\n",
    "                        return 1+dfs(i+1,1,state)\n",
    "                    else:\n",
    "                        return add+dfs(i+1,1,state)\n",
    "                else:\n",
    "                    return dfs(i+1,0,state)\n",
    "            single[x]=(x&1)*2+dfs(1,x&1,0)\n",
    "            union[x]=(x&1)*3+dfs(1,x&1,1)\n",
    "        #预处理结束，接下来写cache\n",
    "        #找到每个pos被袭击的集合\n",
    "        protect=[0]*(max_pos+1)\n",
    "        for i,t in enumerate(time):\n",
    "            protect[position[i]]+=(1<<t)\n",
    "        #真是太麻了，应该注意到前面的太空舱如果不开屏障的话，后面就没机会了，所以应该写个dp之类的会更好一些\n",
    "        f=[[0]*MX for _ in range(max_pos+2)]\n",
    "        #注意到我们有非常令人讨厌的f[-1][...],这里我们外层枚举的范围最好不要改动，之改动内层与f相关的i\n",
    "        #最麻烦的就是，我们务必要知道f[i]的所有状态，这就让我们必须一个个去枚举了，动态规划是这样的\n",
    "        for i in range(max_pos+1):\n",
    "            for j in range(MX):\n",
    "                f[i+1][j]=inf\n",
    "                mask=(MX-1)^j  \n",
    "                # while True: #枚举j的补集mask中的子集pre\n",
    "                #     cost=f[i][pre]+union[j]+single[(mask^pre)&protect[i]]\n",
    "                #     f[i+1][j]=min(f[i+1][j],cost)    \n",
    "                #     if pre==0:\n",
    "                #         break   \n",
    "                #     pre=(pre-1)&mask  \n",
    "                for k in range(mask+1):\n",
    "                    if k|mask==mask:\n",
    "                        cost=f[i][k]+union[j]+single[(mask^k)&protect[i]]\n",
    "                        f[i+1][j]=min(f[i+1][j],cost)\n",
    "        return f[max_pos+1][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "这个可以被省略\n",
    "f[i][j],（保护前i个太空舱）大前提1，\n",
    "第i个太空舱与i+1个舱开启联合屏障的时间集合为j的话，大前提2\n",
    "最小的花费，大前提3\n",
    "守护弱智太空城，气死我了\n",
    "难写的一批\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:\n",
    "        tmp=[i-1 for i in time]\n",
    "        time=tmp\n",
    "        max_time=max(time)\n",
    "        max_pos=max(position)\n",
    "        MX=1<<(max_time+1)\n",
    "        m=max_time+1\n",
    "        #预处理union和single集合,这里主要针对time枚举\n",
    "        #位置集合很好写，时间集合比较麻烦，统统减1映射,完美\n",
    "        #来到了麻烦的地方，怎么处理维持\n",
    "        single=[0]*MX\n",
    "        union=[0]*MX\n",
    "        for x in range(0,MX):\n",
    "            #不会就暴力\n",
    "            def dfs(i:int,pre:int,state:int)->int:\n",
    "                if i==m :return 0\n",
    "                add=2 if state==0 else 3\n",
    "                if x>>i&1 :\n",
    "                    if  pre==1:\n",
    "                        return 1+dfs(i+1,1,state)\n",
    "                    else:\n",
    "                        return add+dfs(i+1,1,state)\n",
    "                else:\n",
    "                    return dfs(i+1,0,state)\n",
    "            single[x]=(x&1)*2+dfs(1,x&1,0)\n",
    "            union[x]=(x&1)*3+dfs(1,x&1,1)\n",
    "        #预处理结束，接下来写cache\n",
    "        #找到每个pos被袭击的集合\n",
    "        protect=[0]*(max_pos+1)\n",
    "        for i,t in enumerate(time):\n",
    "            protect[position[i]]+=(1<<t)\n",
    "        #真是太麻了，应该注意到前面的太空舱如果不开屏障的话，后面就没机会了，所以应该写个dp之类的会更好一些，因为这是互不相干的子问题\n",
    "        f=[[0]*MX for _ in range(max_pos+2)]\n",
    "        #注意到我们有非常令人讨厌的f[-1][...],这里我们外层枚举的范围最好不要改动，之改动内层与f相关的i\n",
    "        #最麻烦的就是，我们务必要知道f[i]的所有状态，这就让我们必须一个个去枚举了，如果想着去贪心的话，就会把自己给绕死。动态规划就是粗暴地把所有可能给枚举一遍，不能够漏掉任何可能\n",
    "        for i in range(max_pos+1):\n",
    "            for j in range(MX):\n",
    "                f[i+1][j]=inf\n",
    "                pre=mask=(MX-1)^j  \n",
    "                while True: #枚举j的补集mask中的子集pre,这个方法比较奇怪\n",
    "                    cost=f[i][pre]+union[j]+single[(mask^pre)&protect[i]]\n",
    "                    f[i+1][j]=min(f[i+1][j],cost)    \n",
    "                    if pre==0:\n",
    "                        break   \n",
    "                    pre=(pre-1)&mask  \n",
    "                # for k in range(mask+1):\n",
    "                #     if k|mask==mask:\n",
    "                #         cost=f[i][k]+union[j]+single[(mask^k)&protect[i]]\n",
    "                #         f[i+1][j]=min(f[i+1][j],cost)\n",
    "        return f[max_pos+1][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
